package tree;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// 翻转二叉树
public class leetcode226 {
    public static void main(String[] args) {
        Integer[] nums = {1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9};
//        Integer[] nums = {1,2,3};
        TreeNode root = createTree(nums);
        root = invertTree(root);
        System.out.println("翻转成功");
    }

    public static TreeNode createTree(Integer[] nums){
        if(nums == null || nums.length == 0) return null;

        TreeNode root = new TreeNode(nums[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int i = 1;
        while(!queue.isEmpty() && i < nums.length){
            TreeNode curr = queue.poll();

            if(i<nums.length && nums[i] != null){
                curr.left = new TreeNode(nums[i]);
                queue.offer(curr.left);
            }
            i++;
            if(i<nums.length && nums[i] != null){
                curr.right = new TreeNode(nums[i]);
                queue.offer(curr.right);
            }
            i++;
        }
        return root;
    }

    public static TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}
